package com.note.feng.leetcode.algorithms.easy.three;

import java.util.HashMap;
import java.util.Map;

public class ThreeHundredEightyNine {

    /**
     * 找不同
     * 给定两个字符串 s 和 t ，它们只包含小写字母。
     *
     * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
     *
     * 请找出在 t 中被添加的字母。
     *
     * 示例 1：
     *
     * 输入：s = "abcd", t = "abcde"
     * 输出："e"
     * 解释：'e' 是那个被添加的字母。
     * 示例 2：
     *
     * 输入：s = "", t = "y"
     * 输出："y"
     *  
     * 提示：
     *
     * 0 <= s.length <= 1000
     * t.length == s.length + 1
     * s 和 t 只包含小写字母
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/find-the-difference
     */
    /**
     *解法：哈希计数
     * 先遍历字符串s，每个字符存进map，并计算出现的次数；
     * 再遍历字符串t，若map中不包含该字符，直接返回该字符，
     * 若包含字符，且map中value为0，说明t比s,多一个字符，直接返回
     * @param s
     * @param t
     * @return
     */
    public char findTheDifference(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            if(!map.containsKey(t.charAt(i))){
                return t.charAt(i);
            }else{
                if(map.get(t.charAt(i)) == 0){
                    return t.charAt(i);
                }else{
                    map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
                }
            }
        }
        return  '0';
    }
}
